<!DOCTYPE html>
<html>
  <head>
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />
    <title>LinkList</title>
    <meta name="viewport" content="width=device-width, initial-scale=1" />
  </head>
  <body>
    <script>
      // 定义链表类
      function LinkList() {
        // 定义节点
        var Node = function (data) {
          this.data = data;
          this.next = null;
        };
        var length = 0; // 长度
        var head = null; // 头节点
        var tail = null; // 尾节点

        // 链表尾部添加一个节点
        this.append = function (data) {
          // 创建新节点
          var new_node = new Node(data);
          if (head === null) {
            head = new_node;
            tail = new_node;
          } else {
            tail.next = new_node;
            tail = new_node;
          }
          length++;
          return true;

          // 另一种实现方式
          // var node = new Node(data);
          // if (head == null) {
          //   head = node;
          // } else {
          //   var current = head;
          //   while (current.next) {
          //     current = current.next;
          //   }
          //   // while 循环执行完之后 ，current 已经是链表最后一项了
          //   current.next = node;
          // }
          // length++;
        };

        //打印链表
        this.print = function () {
          var curr_node = head;
          var linkArr = [];
          while (curr_node) {
            // console.log(curr_node.data);
            linkArr.push(curr_node.data);
            curr_node = curr_node.next; //遍历链表的核心
          }
          console.log(linkArr.join(' -> '));
        };

        //任意位置插入节点
        this.insert = function (index, data) {
          if (index < 0 || index > length) {
            //index不合法
            return false;
          } else if (index === length) {
            // index === length,说明是在尾节点的后面新增,直接调用append方法即可
            return this.append(data);
          } else {
            var new_node = new Node(data);
            if (index === 0) {
              // 如果在头节点前面插入,新的节点就变成了了头节点
              new_node.next = head;
              head = new_node;
            } else {
              // 要插入的位置是index,找到索引为index-1的节点,然后进行连接
              // var insert_index = 1;
              // var curr_node = head;
              // while(insert_index < index){
              //     insert_index++;
              //     curr_node = curr_node.next;
              // }
              // //index=1，curr_node指向head，是第一个节点，
              // var next_node = curr_node.next;   //next_node是第二个节点
              // curr_node.next = new_node;        //第一个节点指向要插入的节点
              // new_node.next = next_node;        //要插入的节点指向第二个节点

              //另一种实现方式
              var pre_node = get_node(index - 1);
              new_node.next = pre_node.next;
              pre_node.next = new_node;
            }
            length++;
            return true;
          }
        };

        //删除指定位置的节点
        this.removeAt = function (index) {
          if (index < 0 || index >= length) {
            //index不合法
            return null;
          } else {
            var del_node = null; //存放被删除的节点
            if (index === 0) {
              del_node = head;
              head = head.next;
            } else {
              var del_index = 0;
              var pre_node = null; //被删除节点的前一个节点
              var curr_node = head; //被删除的节点
              while (del_index < index) {
                del_index++;
                pre_node = curr_node;
                curr_node = curr_node.index;
              }
              del_node = curr_node;
              //被删除节点的前一个节点指向被删除节点的后一个节点
              pre_node.next = curr_node.next;
              //如果被删除的节点是尾节点
              if (curr_node.next === null) {
                tail = pre_node;
              }
            }
            length--;
            del_node.next = null;
            return del_node.data;
          }
        };

        /*
            // 另一种实现方式
            // 删除指定位置的节点
            this.removeAt = function(index){
                // 参数不不合法
                if(index < 0 || index >= length){
                    return null;
                }else{
                    var del_node = null;
                    // 删除的是头节点
                    if(index == 0){
                        // head指向下一个节点
                        del_node = head;
                        head = head.next;
                        // 如果head == null,说明之前链表只有一个节点
                        if(!head){
                            tail = null;
                        }
                    }else{
                        // 找到索引为index-1的节点
                        var pre_node = get_node(index-1);
                        del_node = pre_node.next;
                        pre_node.next = pre_node.next.next;
                        // 如果删除的是尾节点
                        if(del_node.next==null){
                            tail = pre_node;
                        }
                    }
                    length -= 1;
                    del_node.next = null;
                    return del_node.data;
                }
            };*/


        // removeAt(index)   删除某个位置的元素
        // indexOf(data)     获取某个元素的位置
        this.remove = function (data) {
          // length --
          return this.removeAt(this.indexOf(data));
        };

        // 获得指定位置的节点
        var get_node = function (index) {
          if (index < 0 || index >= length) {
            return null;
          }
          var curr_node = head;
          var node_index = index;
          while (node_index-- > 0) {
            curr_node = curr_node.next;
          }
          return curr_node;
        };
        //返回指定位置节点的值
        this.get = function (index) {
          var node = get_node(index);
          if (node) {
            return node.data;
          }
          return null;
        };

        //返回指定元素的索引，如果没有，返回-1；如果有多个相同元素，返回第一个
        this.indexOf = function (data) {
          var index = -1;
          var curr_node = head;
          while (curr_node) {
            index++;
            if (curr_node.data === data) {
              return index;
            } else {
              curr_node = curr_node.next;
            }
          }
          return -1;
        };

        //返回链表的大小
        this.length = function () {
          return length;
        };

        //删除尾节点
        this.remove_tail = function () {
          return this.remove(length - 1);
        };

        //删除头节点
        this.remove_head = function () {
          return this.remove(0);
        };

        //返回链表头节点的值
        this.head = function () {
          return this.get(0);
        };

        //返回链表尾节点的值
        this.tail = function () {
          return this.get(length - 1);
        };

        //判断链表是否为空
        this.isEmpty = function () {
          return this.length === 0;
        };

        //清空链表
        this.clear = function () {
          head = null;
          tail = null;
          length = 0;
        };
      }

      var link = new LinkList();
      link.append(1);
      link.append(4);
      link.append(9);
      link.print();
      console.log(link.head());
    </script>
  </body>
</html>
